package pers.whj.util.tree;

import pers.whj.util.NoSuchElementException;
import pers.whj.util.SerializationUtil;
import pers.whj.util.StringUtil;
import pers.whj.util.list.Queue;
import pers.whj.util.list.QueueList;
import pers.whj.util.list.Stack;

import java.io.Serializable;
import java.lang.reflect.Array;

public class BinaryTreeImpl<T> extends AbstractTree<T> implements BinaryTree<T> {
    public BinaryTreeImpl() {
    }

    @Override
    public T nextSibling(T data) {
        Node<T> node = search(this.root, data);
        checkNode(node);
        Node<T> parent = parentOf(node);
        if (parent == null || parent.right == node) {
            return null;
        } else {
            return parent.right == null ? null : parent.right.data;
        }
    }

    @Override
    public TreePath getTreePath(T data) {
        boolean result = false;
        TreePath treePath = null;
        if (data != null) {
            treePath = new BinaryTreePath();
            result = getTreePath(this.root, treePath, data);
        }
        return result ? treePath : null;
    }

    @Override
    public boolean insert(TreePath treePath, T data) {
        checkInsertData(data);
        if (treePath == null) {
            return false;
        }
        if (treePath.length() == 0) {
            if (size == 0) {
                return insert(new Node<>(data));
            } else {
                return false;
            }
        }
        Node<T> parent = getForInsert(treePath);
        if (parent != null) {
            treePath.skipTo(treePath.length() - 1);
            char dir = treePath.next();
            if (dir == BinaryTreePath.LEFT) {
                if (parent.left == null) {
                    parent.left = new Node<>(data);
                    this.size++;
                    return true;
                }
            } else {
                if (parent.right == null) {
                    parent.right = new Node<>(data);
                    this.size++;
                    return true;
                }
            }
        }
        return false;
    }

    @Override
    public boolean insert(String treePath, T data) {
        checkInsertData(data);
        treePath = BinaryTreePath.normalize(treePath);
        if (treePath.length() == 0) {
            if (size == 0) {
                return insert(new Node<>(data));
            } else {
                return false;
            }
        }
        Node<T> parent = getForInsert(treePath);
        if (parent != null) {
            char dir = treePath.charAt(treePath.length() - 1);
            if (dir == BinaryTreePath.LEFT) {
                if (parent.left == null) {
                    parent.left = new Node<>(data);
                    this.size++;
                    return true;
                }
            } else {
                if (parent.right == null) {
                    parent.right = new Node<>(data);
                    this.size++;
                    return true;
                }
            }
        }
        return false;
    }

    @Override
    public void traversal(Visit<T> visit) {
        inOrder(this.root, visit);
    }

    @Override
    public void traversal(VisitExpand<T> visit) {
        inOrder(this.root, visit, new int[]{0});
    }

    @Override
    public T[] toArray(Class<T> type) {
        return toArrayWithInOrder(type);
    }

    @Override
    public T leftChild(T parent) {
        Node<T> node = search(this.root, parent);
        checkNode(node);
        return node.left == null ? null : node.left.data;
    }

    @Override
    public T rightChild(T parent) {
        Node<T> node = search(this.root, parent);
        checkNode(node);
        return node.right == null ? null : node.right.data;
    }

    @Override
    public boolean insertLeft(T parent, T data) {
        checkInsertData(data);
        Node<T> node = search(this.root, parent);
        checkNode(node);
        if (node.left == null) {
            node.left = new Node<>(data);
            this.size++;
            return true;
        } else {
            return false;
        }
    }

    @Override
    public boolean insertRight(T parent, T data) {
        checkInsertData(data);
        Node<T> node = search(this.root, parent);
        checkNode(node);
        if (node.right == null) {
            node.right = new Node<>(data);
            this.size++;
            return true;
        } else {
            return false;
        }
    }

    @Override
    public boolean removeLeft(T parent) {
        Node<T> node = search(this.root, parent);
        checkNode(node);
        return node.left != null && remove(node.left, node);
    }

    @Override
    public boolean removeRight(T parent) {
        Node<T> node = search(this.root, parent);
        checkNode(node);
        return node.right != null && remove(node.right, node);
    }

    @Override
    public void preOrder(Visit<T> visit) {
        preOrder(this.root, visit);
    }

    @Override
    public void preOrder(VisitExpand<T> visit) {
        preOrder(this.root, visit, new int[]{0});
    }

    @Override
    public void inOrder(Visit<T> visit) {
        inOrder(this.root, visit);
    }

    @Override
    public void inOrder(VisitExpand<T> visit) {
        inOrder(this.root, visit, new int[]{0});
    }

    @Override
    public void postOrder(Visit<T> visit) {
        postOrder(this.root, visit);
    }

    @Override
    public void postOrder(VisitExpand<T> visit) {
        postOrder(this.root, visit, new int[]{0});
    }

    @Override
    public void levelOrder(Visit<T> visit) {
        levelOrder(this.root, visit);
    }

    @Override
    public void levelOrder(VisitExpand<T> visit) {
        levelOrder(this.root, visit);
    }

    @Override
    @SuppressWarnings({"unchecked"})
    public T[] toArrayWithPreOrder(Class<T> type) {
        Object[] array = (Object[]) Array.newInstance(type, this.size);
        preOrder(this.root, (data, index) -> {
            array[index] = data;
            return true;
        }, new int[]{0});
        return (T[]) array;
    }

    @Override
    @SuppressWarnings({"unchecked"})
    public T[] toArrayWithInOrder(Class<T> type) {
        Object[] array = (Object[]) Array.newInstance(type, this.size);
        inOrder(this.root, (data, index) -> {
            array[index] = data;
            return true;
        }, new int[]{0});
        return (T[]) array;
    }

    @Override
    @SuppressWarnings({"unchecked"})
    public T[] toArrayWithPostOrder(Class<T> type) {
        Object[] array = (Object[]) Array.newInstance(type, this.size);
        postOrder(this.root, (data, index) -> {
            array[index] = data;
            return true;
        }, new int[]{0});
        return (T[]) array;
    }

    @Override
    @SuppressWarnings({"unchecked"})
    public T[] toArrayWithLevelOrder(Class<T> type) {
        Object[] array = (Object[]) Array.newInstance(type, this.size);
        if (this.root != null) {
            Queue<Node<T>> queue = new QueueList<>();
            queue.offer(this.root);
            int index = 0;
            Node<T> node;
            while (!queue.isEmpty()) {
                node = queue.poll();
                array[index++] = node.data;
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
        }
        return (T[]) array;
    }

    @Override
    public boolean buildCompleteBinaryTree(T[] data) {
        if (data == null) {
            return false;
        }
        if (data.length > 0) {
            clear();
            this.root = new Node<>(data[0]);
            QueueList<Node<T>> queue = new QueueList<>();
            queue.offer(this.root);
            int index = 1;
            Node<T> tmp;
            while (index < data.length) {
                tmp = queue.poll();
                tmp.left = new Node<>(data[index]);
                queue.offer(tmp.left);
                index++;
                if (index < data.length) {
                    tmp.right = new Node<>(data[index]);
                    queue.offer(tmp.right);
                    index++;
                }
            }
        }
        return true;
    }

    @Override
    public boolean buildByPreOrderAndInOrder(T[] preOrder, T[] inOrder) {
        if (preOrder == null || inOrder == null || preOrder.length != inOrder.length) {
            return false;
        }
        clear();
        this.root = newNode(null);
        buildByPreOrderAndInOrder(this.root, preOrder, 0, inOrder, 0, preOrder.length);
        return true;
    }

    @Override
    public boolean buildByPostOrderAndInOrder(T[] postOrder, T[] inOrder) {
        if (postOrder == null || inOrder == null || postOrder.length != inOrder.length) {
            return false;
        }
        clear();
        this.root = newNode(null);
        buildByPostOrderAndInOrder(this.root, postOrder, 0, inOrder, 0, postOrder.length);
        return true;
    }

    @Override
    public boolean buildByLevelOrderAndInOrder(T[] levelOrder, T[] inOrder) {
        if (levelOrder == null || inOrder == null || levelOrder.length != inOrder.length) {
            return false;
        }
        clear();
        this.root = newNode(null);
        buildByLevelOrderAndInOrder(this.root, levelOrder, inOrder, 0, inOrder.length - 1);
        return true;
    }

    @Override
    public String convertToGenList() throws Exception {
        StringBuilder builder = new StringBuilder();
        if (this.root != null) {
            Class<?> clazz = this.root.data.getClass();
            if (clazz.equals(Character.class) || clazz.equals(Integer.class)) {
                convert(builder, this.root);
            } else {
                convertAndSerialize(builder, this.root);
            }
        }
        return builder.toString();
    }

    protected void convert(StringBuilder builder, Node<T> node) {
        if (node != null) {
            builder.append(node.data.toString());
            if (node.left != null || node.right != null) {
                builder.append('(');
                convert(builder, node.left);
                builder.append(',');
                convert(builder, node.right);
                builder.append(')');
            }
        }
    }

    protected void convertAndSerialize(StringBuilder builder, Node<T> node) throws Exception {
        if (node != null) {
            builder.append(StringUtil.bytesToBase64(SerializationUtil.serialize((Serializable) node.data)));
            if (node.left != null || node.right != null) {
                builder.append('(');
                convertAndSerialize(builder, node.left);
                builder.append(',');
                convertAndSerialize(builder, node.right);
                builder.append(')');
            }
        }
    }

    @Override
    protected int size(Node<T> node) {
        if (node != null) {
            return size(node.left) + size(node.right) + 1;
        }
        return 0;
    }

    @Override
    protected int height(Node<T> node) {
        if (node != null) {
            int i = height(node.left);
            int j = height(node.right);
            return Math.max(i, j) + 1;
        }
        return 0;
    }

    @Override
    protected Node<T> parentOf(Node<T> node) {
        if (node == null || node == root) {
            return null;
        } else {
            return parentOf(this.root, node);
        }
    }

    protected Node<T> parentOf(Node<T> parent, Node<T> node) {
        if (parent == null) {
            return null;
        }
        if (parent.left == node || parent.right == node) {
            return parent;
        }
        Node<T> tmp = parentOf(parent.left, node);
        if (tmp == null) {
            tmp = parentOf(parent.right, node);
        }
        return tmp;
    }

    @Override
    protected Node<T> search(Node<T> node, T data) {
        if (data == null || node == null) {
            return null;
        }
        if (node.data.equals(data)) {
            return node;
        }
        Node<T> tmp = search(node.left, data);
        if (tmp == null) {
            tmp = search(node.right, data);
        }
        return tmp;
    }

    @Override
    protected Node<T> get(TreePath treePath) {
        if (treePath == null) {
            return null;
        }
        treePath.reset();
        Node<T> node = this.root;
        while (treePath.hasNext() && node != null) {
            if (treePath.next() == BinaryTreePath.LEFT) {
                node = node.left;
            } else {
                node = node.right;
            }
        }
        return node;
    }

    @Override
    protected Node<T> get(String treePath) {
        if (treePath == null) {
            return null;
        }
        treePath = BinaryTreePath.normalize(treePath);
        Node<T> node = this.root;
        int i = 0;
        while (i < treePath.length() && node != null) {
            if (treePath.charAt(i) == BinaryTreePath.LEFT) {
                node = node.left;
            } else {
                node = node.right;
            }
            i++;
        }
        return node;
    }

    @Override
    protected Node<T> getForInsert(TreePath treePath) {
        if (treePath == null) {
            return null;
        }
        treePath.reset();
        Node<T> node = this.root;
        int i = 0;
        while (i < treePath.length() - 1 && node != null) {
            if (treePath.next() == BinaryTreePath.LEFT) {
                node = node.left;
            } else {
                node = node.right;
            }
            i++;
        }
        return node;
    }

    @Override
    protected Node<T> getForInsert(String treePath) {
        if (treePath == null) {
            return null;
        }
        treePath = BinaryTreePath.normalize(treePath);
        Node<T> node = this.root;
        int i = 0;
        while (i < treePath.length() - 1 && node != null) {
            if (treePath.charAt(i) == BinaryTreePath.LEFT) {
                node = node.left;
            } else {
                node = node.right;
            }
            i++;
        }
        return node;
    }

    protected boolean getTreePath(Node<T> node, TreePath treePath, T data) {
        // assert data is not null
        if (node == null) {
            return false;
        }
        if (data.equals(node.data)) {
            return true;
        }
        boolean result;
        treePath.append(BinaryTreePath.LEFT);
        result = getTreePath(node.left, treePath, data);
        if (result) {
            return true;
        } else {
            treePath.delete();
        }
        treePath.append(BinaryTreePath.RIGHT);
        result = getTreePath(node.right, treePath, data);
        if (!result) {
            treePath.delete();
        }
        return result;
    }

    @Override
    protected boolean insert(Node<T> node) {
        // assert node is not null
        if (this.size <= 2) {
            if (this.size == 0) {
                this.root = node;
            } else if (this.size == 1) {
                this.root.left = node;
            } else {
                if (this.root.left == null) {
                    this.root.left = node;
                } else {
                    this.root.right = node;
                }
            }
            this.size++;
            return true;
        }
        return false;
    }

    @Override
    protected boolean remove(Node<T> node) {
        return remove(node, parentOf(node));
    }

    @Override
    protected boolean remove(Node<T> node, Node<T> parent) {
        if (parent == null) {
            clear();
        } else {
            int num = size(node);
            if (parent.left == node) {
                parent.left = null;
            } else {
                parent.right = null;
            }
            this.size -= num;
        }
        return true;
    }

    @Override
    protected void clear(Node<T> node) {
        if (node != null) {
            clear(node.left);
            clear(node.right);
            node.data = null;
            node.left = node.right = null;
            this.size--;
        }
    }

    protected void preOrder(Node<T> node, Visit<T> visit) {
        if (node != null) {
            visit.visit(node.data);
            preOrder(node.left, visit);
            preOrder(node.right, visit);
        }
    }

    protected boolean preOrder(Node<T> node, VisitExpand<T> visit, int[] index) {
        boolean flag = true;
        if (node != null) {
            flag = visit.visit(node.data, index[0]++);
            if (flag) {
                flag = preOrder(node.left, visit, index);
                if (flag) {
                    flag = preOrder(node.right, visit, index);
                }
            }
        }
        return flag;
    }

    protected void inOrder(Node<T> node, Visit<T> visit) {
        if (node != null) {
            inOrder(node.left, visit);
            visit.visit(node.data);
            inOrder(node.right, visit);
        }
    }

    protected boolean inOrder(Node<T> node, VisitExpand<T> visit, int[] index) {
        boolean flag = true;
        if (node != null) {
            flag = inOrder(node.left, visit, index);
            if (flag) {
                flag = visit.visit(node.data, index[0]++);
                if (flag) {
                    flag = inOrder(node.right, visit, index);
                }
            }
        }
        return flag;
    }

    protected void postOrder(Node<T> node, Visit<T> visit) {
        if (node != null) {
            postOrder(node.left, visit);
            postOrder(node.right, visit);
            visit.visit(node.data);
        }
    }

    protected boolean postOrder(Node<T> node, VisitExpand<T> visit, int[] index) {
        boolean flag = true;
        if (node != null) {
            flag = postOrder(node.left, visit, index);
            if (flag) {
                flag = postOrder(node.right, visit, index);
                if (flag) {
                    flag = visit.visit(node.data, index[0]++);
                }
            }
        }
        return flag;
    }

    protected void levelOrder(Node<T> node, Visit<T> visit) {
        if (node != null) {
            Queue<Node<T>> queue = new QueueList<>();
            queue.offer(node);
            while (!queue.isEmpty()) {
                node = queue.poll();
                visit.visit(node.data);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
        }
    }

    protected void levelOrder(Node<T> node, VisitExpand<T> visit) {
        if (node != null) {
            Queue<Node<T>> queue = new QueueList<>();
            queue.offer(node);
            int index = 0;
            while (!queue.isEmpty()) {
                node = queue.poll();
                if (!visit.visit(node.data, index++)) {
                    return;
                }
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
        }
    }

    protected void buildByPreOrderAndInOrder(Node<T> node, T[] preOrder, int preStart, T[] inOrder, int inStart, int length) {
        if (length == 0) {
            return;
        }
        int k = 0;
        while (k < length && preOrder[preStart] != inOrder[inStart + k]) {
            k++;
        }
        if (k == length) {
            throwExceptionWhileBuild();
        }
        node.data = preOrder[preStart];
        int leftLength = k;
        int rightLength = length - k - 1;
        if (leftLength > 0) {
            node.left = newNode(null);
            buildByPreOrderAndInOrder(node.left, preOrder, preStart + 1, inOrder, inStart, leftLength);
        }
        if (rightLength > 0) {
            node.right = newNode(null);
            buildByPreOrderAndInOrder(node.right, preOrder, preStart + k + 1, inOrder, inStart + k + 1, rightLength);
        }
    }

    protected void buildByPostOrderAndInOrder(Node<T> node, T[] postOrder, int postStart, T[] inOrder, int inStart, int length) {
        if (length == 0) {
            return;
        }
        int k = 0;
        while (k < length && postOrder[postStart + length - 1] != inOrder[inStart + k]) {
            k++;
        }
        if (k == length) {
            throwExceptionWhileBuild();
        }
        node.data = postOrder[postStart + length - 1];
        int leftLength = k;
        int rightLength = length - k - 1;
        if (leftLength > 0) {
            node.left = newNode(null);
            buildByPostOrderAndInOrder(node.left, postOrder, postStart, inOrder, inStart, leftLength);
        }
        if (rightLength > 0) {
            node.right = newNode(null);
            buildByPostOrderAndInOrder(node.right, postOrder, postStart + k, inOrder, inStart + k + 1, rightLength);
        }
    }

    @SuppressWarnings("unchecked")
    protected void buildByLevelOrderAndInOrder(Node<T> node, T[] levelOrder, T[] inOrder, int start, int end) {
        if (levelOrder.length == 0) {
            return;
        }
        int k = start;
        while (k <= end && levelOrder[0] != inOrder[k]) {
            k++;
        }
        if (k > end) {
            throwExceptionWhileBuild();
        }
        node.data = levelOrder[0];
        Object[] leftOrder = (Object[]) Array.newInstance(levelOrder[0].getClass(), k - start);
        Object[] rightOrder = (Object[]) Array.newInstance(levelOrder[0].getClass(), end - k);
        int leftIndex = 0;
        int rightIndex = 0;
        for (int i = 1; i < levelOrder.length; i++) {
            int j;
            for (j = start; j < k; j++) {
                if (levelOrder[i] == inOrder[j]) {
                    leftOrder[leftIndex++] = levelOrder[i];
                    break;
                }
            }
            if (j == k) {
                rightOrder[rightIndex++] = levelOrder[i];
            }
        }
        if (k - start > 0) {
            node.left = newNode(null);
            buildByLevelOrderAndInOrder(node.left, (T[]) leftOrder, inOrder, start, k - 1);
        }
        if (end - k > 0) {
            node.right = newNode(null);
            buildByLevelOrderAndInOrder(node.right, (T[]) rightOrder, inOrder, k + 1, end);
        }
    }

    protected void throwExceptionWhileBuild() {
        throw new NoSuchElementException("can't find the equal element while building");
    }

    public static void createByCharacterGenList(String genList, BinaryTreeImpl<Character> tree) {
        if (genList == null || genList.length() == 0 || tree == null) {
            return;
        }
        tree.clear();
        tree.root = tree.newNode(null);
        Stack<Node<Character>> stack = new QueueList<>();
        int index = 0;
        char c;
        boolean isLeftChild = true;
        Node<Character> node = null;
        while (index < genList.length()) {
            c = genList.charAt(index);
            index++;
            switch (c) {
                case '(':
                    stack.push(node);
                    isLeftChild = true;
                    break;
                case ')':
                    stack.pop();
                    break;
                case ',':
                    isLeftChild = false;
                    break;
                default:
                    if (tree.root.data == null) {
                        tree.root.data = c;
                        node = tree.root;
                    } else {
                        node = tree.newNode(c);
                        if (isLeftChild) {
                            stack.peek().left = node;
                        } else {
                            stack.peek().right = node;
                        }
                    }
            }
        }
    }

    public static void createByIntegerGenList(String genList, BinaryTreeImpl<Integer> tree) {
        if (genList == null || genList.length() == 0 || tree == null) {
            return;
        }
        tree.clear();
        tree.root = tree.newNode(null);
        Stack<Node<Integer>> stack = new QueueList<>();
        StringBuilder builder = new StringBuilder();
        int index = 0;
        char c;
        boolean isLeftChild = true;
        int obj;
        Node<Integer> node;
        while (index < genList.length()) {
            c = genList.charAt(index);
            index++;
            switch (c) {
                case '(':
                    obj = getObject(builder.toString());
                    builder = new StringBuilder();
                    if (stack.isEmpty()) {
                        tree.root.data = obj;
                        stack.push(tree.root);
                    } else {
                        node = new Node<>(obj);
                        if (isLeftChild) {
                            stack.peek().left = node;
                        } else {
                            stack.peek().right = node;
                        }
                        stack.push(node);
                    }
                    isLeftChild = true;
                    break;
                case ')':
                    node = stack.pop();
                    if (builder.length() > 0) {
                        obj = getObject(builder.toString());
                        builder = new StringBuilder();
                        node.right = new Node<>(obj);
                    }
                    break;
                case ',':
                    if (builder.length() > 0) {
                        obj = getObject(builder.toString());
                        builder = new StringBuilder();
                        stack.peek().left = new Node<>(obj);
                    }
                    isLeftChild = false;
                    break;
                default:
                    builder.append(c);
            }
        }
    }

    public static <T> void createByObjectGenList(String genList, Class<T> clazz, BinaryTreeImpl<T> tree) throws Exception {
        if (genList == null || genList.length() == 0 || tree == null) {
            return;
        }
        tree.clear();
        tree.root = tree.newNode(null);
        Stack<Node<T>> stack = new QueueList<>();
        StringBuilder builder = new StringBuilder();
        int index = 0;
        char c;
        boolean isLeftChild = true;
        T obj;
        Node<T> node;
        while (index < genList.length()) {
            c = genList.charAt(index);
            index++;
            switch (c) {
                case '(':
                    obj = getObject(builder.toString(), clazz);
                    builder = new StringBuilder();
                    if (stack.isEmpty()) {
                        tree.root.data = obj;
                        stack.push(tree.root);
                    } else {
                        node = new Node<>(obj);
                        if (isLeftChild) {
                            stack.peek().left = node;
                        } else {
                            stack.peek().right = node;
                        }
                        stack.push(node);
                    }
                    isLeftChild = true;
                    break;
                case ')':
                    node = stack.pop();
                    if (builder.length() > 0) {
                        obj = getObject(builder.toString(), clazz);
                        builder = new StringBuilder();
                        node.right = new Node<>(obj);
                    }
                    break;
                case ',':
                    if (builder.length() > 0) {
                        obj = getObject(builder.toString(), clazz);
                        builder = new StringBuilder();
                        stack.peek().left = new Node<>(obj);
                    }
                    isLeftChild = false;
                    break;
                default:
                    builder.append(c);
            }
        }
        if (builder.length() > 0) {
            obj = getObject(builder.toString(), clazz);
            tree.root.data = obj;
        }
    }

    private static Integer getObject(String src) {
        return Integer.decode(src);
    }

    private static <T> T getObject(String src, Class<T> clazz) throws Exception {
        return SerializationUtil.deserialize(StringUtil.base64ToBytes(src), clazz);
    }
}